from typing import *
from heapq import *


class Solution:

    def minInterval(self, intervals: List[List[int]],
                    queries: List[int]) -> List[int]:
        idx = [i for i in range(len(queries))]
        idx.sort(key=lambda a: queries[a])
        intervals.sort(key=lambda a: a[0])
        q = []
        k = 0
        ans = [-1 for _ in range(len(queries))]
        for i in range(len(queries)):
            index = idx[i]
            query = queries[index]
            while k < len(intervals) and intervals[k][0] <= query:
                l, r = intervals[k]
                heappush(q, (r - l + 1, r))
                k += 1
            while len(q) > 0 and q[0][1] < query:
                heappop(q)
            if len(q) != 0:
                ans[index] = q[0][0]
        return ans


s = Solution()

print(s.minInterval([[4, 5], [5, 8], [1, 9], [8, 10], [1, 6]],
                    [7, 9, 3, 9, 3]))
print(s.minInterval([[2, 3], [2, 5], [1, 8], [20, 25]], [2, 19, 5, 22]))
print(s.minInterval([[1, 4], [2, 4], [3, 6], [4, 4]], [2, 3, 4, 5]))
